package com.zdp.leetcodeMiddle;


/*
* 题目描述：
* 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
限制：
0 <= 数组长度 <= 10^5

注意：本题与主站 121 题相同：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 股票的最大利润_offer63 {
    public static void main(String[] args) {
        股票的最大利润_offer63 demo = new 股票的最大利润_offer63();
        int[] prices = new int[] {
                7,1,5,3,6,4
        };
        System.out.println(demo.maxProfit(prices));
    }

    /*
     * 解题思路： 一次买卖股票的最大利润   那应该是 前后差值最大的两个数
     * 与之前那题  最佳买卖股票时机含冷冻期_309 不同  之前那题是可以多次买入卖出，利用动态规划可以求解（三个状态）
     * */
    public int maxProfit(int[] prices) {
        int length = prices.length;
        if(length == 0){
            return 0;
        }
        int[][] dp = new int[length][2];
        // 两个状态 持有  0 和 不持有  1  持有时可以卖出 不持有时可以买入
        /*
         * dp[i][0] : 当前不持有 ： 尽可能大
         * dp[i][1] : 当前持有 ： 尽可能小
         * dp[i][0] = Math.max( dp[i-1][1] + prices[i],dp[i-1][0] ) 当天不持有有两种可能，今天刚卖，和之前就不持有
         *  dp[i][1] = Math.max(dp[i-1][1],0-prices[i]); 当前持有,因为只有一次买入和卖出的机会，所以不管在哪天买入 本金都会是0
         * */
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        int result = 0;
        for(int i =1;i<length;i++){
            // 当前不持有
            dp[i][0] =  Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            // 当前持有,因为只有一次买入和卖出的机会，所以不管在哪天买入 本金都会是0
            dp[i][1] = Math.max(dp[i-1][1],0-prices[i]);
            result = Math.max(result,dp[i][0]);
        }

        return result;
    }

    /*
    * 官方题解： 假设i为当前遍历到的位置 用一个变量来记录 0~i中的最小值 min
    *  当 nums[j] j 位于 mini ~ i 之中  当 nums[j] > min 时，计算其差值，
    * 类似滑动窗口吧； ----> mini 是窗口的其实位置，当nums[j]>min时，就将窗口右扩
    * 当 nums[j] < min时，窗口的左边界变为j
    * */
    public int maxProfit1(int[] prices) {
        int result = 0;
        int min = Integer.MAX_VALUE;
        for(int i =0; i < prices.length ; i++){
            if( prices[i] <= min){
                min = prices[i];
            }else{
                result = Math.max(result,prices[i] - min);
            }
        }
        return result;
    }
}
